#include "Tree.h"
#include "Queue.h"

// 前序遍历---根左右

void preOrder (BTNode* root)
{

    if (root == NULL)
    {

        printf ("NULL ") ;

        return ;

    }

    printf ("%c " , root -> data) ;

    preOrder (root -> left) ;

    preOrder (root -> right) ;

}

// 中序遍历---左根右

void inOrder (BTNode* root)
{

    if (root == NULL)
    {

        printf ("NULL ") ;

        return ;

    }

    inOrder (root -> left) ;

    printf ("%c " , root -> data) ;

    inOrder (root -> right) ;

}

// 后序遍历---左右根

void postOrder (BTNode* root)
{

    if (root == NULL)
    {

        printf ("NULL ") ;

        return ;

    }

    postOrder (root -> left) ;

    postOrder (root -> right) ;

    printf ("%c " , root -> data) ;

}

// 层序遍历

void leverOrder (BTNode* root)
{

    Queue q ;

    QInit (&q) ;

    QPush (&q , root) ;

    while (!QEmpty (&q))
    {

        // 取队头,出队头

        BTNode* top = QFront (&q) ;

        QPop (&q) ;

        printf ("%c " , top -> data) ;

        // 入队---队尾

        if (top -> left)
        {

            QPush (&q , top -> left) ;

        }

        if (top -> right)
        {

            QPush (&q , top -> right) ;

        }
        
    }

    QDestory (&q) ;

}

// 二叉树节点个数

// int size = 0 ;

// int BinaryTreeSize (BTNode* root)
// {

//     if (root == NULL)
//     {

//         return 0 ;

//     }
    
//     // 节点非空,+1

//     size++ ;

//     BinaryTreeSize (root -> left) ;

//     BinaryTreeSize (root -> right) ;

//     return size ;

// }

// int BinaryTreeSize (BTNode* root , int* psize)
// {

//     if (root == NULL)
//     {

//         return 0 ;

//     }

//     // 节点非空,+1

//     (*psize)++ ;

//     BinaryTreeSize (root -> left , psize) ;

//     BinaryTreeSize (root -> right , psize) ;

//     return *psize ;

// }

int BinaryTreeSize (BTNode* root)
{

    if (root == NULL)
    {

        return 0 ;

    }

    return 1 + BinaryTreeSize (root -> left) + BinaryTreeSize (root -> right) ;

}

// 二叉树叶子节点的个数

int BinaryTreeLeafSize (BTNode* root)
{

    if (root == NULL)
    {

        return 0 ;

    }

    if (root -> left == NULL && root -> right == NULL)
    {

        return 1 ;

    }

    return BinaryTreeLeafSize (root -> left) + BinaryTreeLeafSize (root -> right) ;

}

// 二叉树第k节点的个数

int BinaryTreeLevelKSize (BTNode* root , int k)
{

    if (root == NULL)
    {

        return 0 ;

    }

    if (k == 1)
    {

        return 1 ;

    }

    return BinaryTreeLevelKSize (root -> left , k - 1) + BinaryTreeLevelKSize (root -> right , k - 1) ;

}

// 二叉树的深度/高度

int BinaryTreeDepth (BTNode* root)
{

    if (root == NULL)
    {

        return 0 ;

    }

    int leftDep = BinaryTreeDepth (root -> left) ;

    int rightDep = BinaryTreeDepth (root -> right) ;

    return 1 + (leftDep > rightDep ? leftDep : rightDep) ;

}

// 二叉树的查找

BTNode* BinaryTreeFind (BTNode* root , BTDataType x)
{


    if (root == NULL)
    {

        return NULL ;

    }

    if (root -> data == x)
    {

        return root ;

    }

    BTNode* leftFind = BinaryTreeFind (root -> left , x) ;

    if (leftFind)
    {

        return leftFind ;

    } 

    BTNode* rightFind = BinaryTreeFind (root -> right , x) ;

    if (rightFind)
    {

        return rightFind ;

    }

    return NULL ;

}

// 二叉树的销毁

void BinaryTreeDestory (BTNode** root)
{

    if (*root == NULL)
    {

        return ;

    }

    BinaryTreeDestory (&((*root) -> left)) ;

    BinaryTreeDestory (&((*root) -> right)) ;

    free (*root) ;

    *root = NULL ;

}